package crawler;

/**
 * Created by User on 2017/12/14.
 */
public class App {


    public static void main(String[] args) {

        System.out.println(lcs("123456", "2134513125321"));


    }



    protected static int lcs(String x, String y) {

        int M = x.length();
        int N = y.length();
        if (M == 0 || N == 0) {
            return 0;
        }
        int[][] opt = new int[M + 1][N + 1];

        for (int i = M - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                if (x.charAt(i) == y.charAt(j)) {
                    opt[i][j] = opt[i + 1][j + 1] + 1;
                } else {
                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
                }
            }
        }

        printOpt(opt);

        return opt[0][0];
    }

    private static void printOpt(int[][] opt) {
        int yLen = opt[0].length;
        int xLen = opt.length;
        for (int x = 0; x < xLen; x++) {
            for (int y = 0; y < yLen; y++) {
                int value = opt[x][y];
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }


}
